﻿namespace LeetCodeProject._0001_1000._001_100._31_40._040;

public class Solution
{
    List<IList<int>> result = new List<IList<int>>();

    public IList<IList<int>> CombinationSum2(int[] candidates, int target)
    {
        Array.Sort(candidates);
        recrusion(candidates, target, 0, new List<int>(), 0);
        return result;
    }

    private void recrusion(int[] candidates, int target, int sum, IList<int> item, int begin)
    {
        if (sum == target)
        {
            result.Add(new List<int>(item));
            return;
        }

        for (int i = begin; i < candidates.Length; i++)
        {
            if (sum < target)
            {
                if (i > begin && candidates[i] == candidates[i - 1]) continue;
                sum += candidates[i];
                item.Add(candidates[i]);
                recrusion(candidates, target, sum, item, i + 1);
                sum -= candidates[i];
                item.RemoveAt(item.Count - 1);
            }
        }
    }
}